In this paper, we propose a channel assignment scheme for integrated voice and data traffic in reservation multiple access protocol. In the proposed scheme, a voice packet never contends with a data packet and takes over the slot which is previously assigned to a data packet. Thus, a larger number of voice terminals can be accommodated without degradation of quality and throughput even in the situation that data were integrated. We evaluate the voice packet dropping probability, throughput and packet delay through computer simulation. The results show that the proposed scheme has better performance than the conventional PRMA and DQRUMA systems.

We experimentally studied the polarization mode dispersion (PMD) tolerance of an feed-forward equalizer (FFE) electronic dispersion compensation (EDC) IC in the absence of adaptive control, in 43-Gbit/s RZ-DQPSK transmission. Using a 3-tap FFE IC composed of InP HBTs, differential group delay (DGD) tolerance at a 2-dB Q penalty is shown to be extended from 25 ps to up to 29 ps. When a polarization scrambler is used, the tolerance is further extended to 31 ps. This value is close to the tolerance obtained with adaptive control, without a polarization scrambler.

For the expansion of using the integral equation methods on wave-field analysis, a new method called "Source and Radiation Field Solution" is suggested. This solution uses a couple of integral equations. One of them is the traditional integral expression giving the scattered field from the wave source, another is newly proposed one which expresses the wave source from both of the source and the scattered field, by using the conjugate Green function expression. Therefore this method can derive both of the source and the scattered field at the same time by coupled two equations. For showing the effect of this method, we analyze scattering problems for dielectrics in this paper.

In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

We study effects of preamplifier nonlinearity on polarization mode dispersion (PMD) equalization performance of feed-forward equalizer (FFE) electronic dispersion compensation (EDC) IC. We have shown that a nonlinear limiting amplifier can be used as a preamplifier for FFE EDC IC for a 6-dB dynamic range.

Connectivity (of node-to-node) is generally used to examine the robustness of graphs. When telecommunication network switches are integrated into logical switching areas, we should examine node-to-area connectivity rather than node-to-node connectivity. In a previous paper, we proposed node-to-area (NA) connectivity using area (subset of nodes) graph. In this paper, we consider a further constraint: "there is a path that does not include other nodes in the source node area." We call this property, directly NA-connected. Application of this constraint makes telecommunications networks robust against locally striking disasters. The problem of finding the maximum number of edge deletions that still preserves the direct NA-connection is shown to be NP-hard. It was shown in our previous paper that an NA-connected spanning tree is easily found; this paper shows that the problem of finding a directly NA-connected spanning tree is also NP-hard. We propose an O(|E||X|) approximation algorithm that finds a directly NA-connected spanning subgraph with an edge nummber not exceeding 2|V|3 for any NA-connected area graph that satisfies a described simple condition. (|V|,|E|,and |X| are the numbers of nodes, edges, and areas, respectively.)

We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In this paper, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.

Streak cameras are now widely used for measurements of ultra short phenomena, such as those in semi conductor luminescence and plasma gaseous discharge. To further improve the temporal resolution and carry out higher-dimensional measurements, it is necessary to understand the electron beam behavior in detail. Thus, numerical simulations play an important role in the analysis of the streak camera. The authors have been working on the development of a numerical simulation code that uses the finite difference method (FDM) for electric field analysis, the Runge-Kutta (R-K) method for charged particle motion determination, and the particle-in-cell (PIC) method for charge density calculation. However, the use of the PIC method leads to inaccuracy in the charge density calculation in cases of high-density electron beams. To improve the accuracy of the conventional analysis of the streak camera, we perform the boundary element (BE) analysis of the streak camera.

We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] for linear cellular automata, we extend the notion to general cellular automata on groups and investigated their properties. We observe the all unions and compositions generated by one-dimensional 2-neighborhood cellular automata over Z2 including non-linear cellular automata. Next we prove that the composition is right-distributive over union, but is not left-distributive. Finally, we conclude by showing reformulation of our definition of cellular automata on group which admit more than three states. We also show our formulation contains the representation using formal power series for linear cellular automata in Manzini [6].

We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.

We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kamiski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n2) recoloring steps. We remark that the upper bound O(n2) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n2) recoloring steps.

Distributed array radars consist of multiple sub-arrays separated by tens to hundreds of wavelengths and can match narrow beamwidths with large-aperture, high-gain antennas. The physical independence of the sub-arrays contributes to significant structure flexibility and is one of the advantages of such radars. However, a typical problem is the grating lobes in the digital beam forming (DBF) beam pattern. Unfortunately, the need to suppress the generation of grating lobes makes the design of acceptable sub-array arrangements very difficult. A sigma-delta beam former direction of arrival (DOA) estimation method is proposed in this study to solve this problem. The proposed method performs DOA estimation by acquiring the difference signals in addition to the sum signals of all sub-arrays. The difference signal is typically used for monopulse DOA estimation in the phased array radar. The sigma-delta beamformer simultaneously has both advantages of DOA estimations using a distributed array with a large aperture length and using a sub-array that is not affected by the grating lobe. The proposed method can improve the DOA estimation accuracy over the conventional method under grating lobe situations and help the distributed array radar achieve flexibility in the sub-array arrangement. Numerical simulations are presented to verify the effectiveness of the proposed DOA estimation method.

The (InAs)1(GaAs)n short period superlattice (SPS) channel 2DEGFET's with 0.2 µm T-Shaped gates have been successfully fabricated on a GaAs substrate for the first time, and DC and RF performances of the superlattice channel devices have been investigated. Compared to conventional InGaAs alloy channel devices, excellent results in both DC and RF characteristics have been obtained for the SPS channel devices. The dependence of the layer index n for (InAs)1(GaAs)n on device performances has been also investigated. The (InAs)1(GaAs)4 channel samples have shown higher cut-off frequencies as well as superior noise performances compared to those for the (InAs)1(GaAs)5 channel samples. The best noise figure of 0.55 dB with an associated gain of 11.26 dB has been obtained at 12 GHz. The superior performances obtained are due to the improved electron transport properties of (InAs)1(GaAs)n SPS compared to those of InGaAs alloy. These results indicate a great potential of SPS channel structures for high frequency low noise device applications.

In STS-based mapping, it is necessary to obtain the correct order of probes in a DNA sequence from a given set of fragments or an equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has a consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order uniquely determines the correct order of the probes. Unfortunately this does not hold if the data include errors, and this has been a popular research target in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens because of the lack of some information regarding the data, but almost no further investigation has previously been made. In this paper, we define a measure of such imperfectness of the data as the minimum amount of the additional fragments that are needed to uniquely fix the probe order. Polynomial-time algorithms to compute such additional fragments of the minimum cost are presented. A computer simulation using genes of human chromosome 20 is also noted.

Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f0 and fr of G, and asked whether there exists a sequence of list edge-colorings of G between f0 and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer k ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer k ≥ 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if k ≤ 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: for every integer k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.

Interactive audio-video applications over IP networks have subjective tradeoffs between fidelity and latency owing to packet buffering at the receiver. Increasing the buffering time improves the fidelity, whereas it degrades the latency. This paper makes the subjective tradeoff between fidelity and latency clear in a quantitative way. In addition, we examine the effect of tasks on the subjective tradeoff. In evaluating the effect of tasks, we use two tasks according to ITU-T Recommendation P.920. An experiment was conducted to measure user-level QoS of an interactive application with the psychometric methods. We then investigate the subjective tradeoff quantitatively by QoS mapping. The experimental results confirm that there exists the buffering time which makes user-level QoS the highest. The results also show that the optimum buffering time depends on the kind of task.

A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

This paper describes an adaptively weighted code division multiplexing (AW-CDM) system, in other words, power controlled spread-spectrum multiplexing system and describes its application to hierarchical digital broadcasting of television signals. The AW-CDM, being combined with multi-resolutional video encoder, can provide such a hierarchical transmission that allows both high quality services for fixed receivers and reduced quality services for mobile/portable receivers. The carrier and the clock are robustly regenerated by using a spread-spectrum multiplexed pseudorandom noise (PN) sounder as a reference in the receiver. The PN reference is also used for Rake combining with signals via different paths, and for adaptive equalization (EQ). In a prototype AW-CDM modem, three layers of hierarchical video signals (highs: 5.91Mbps, middles: 1.50Mbps, and lows: 0.46 Mbps) are divided into a pair of 64 orthogonal spread-spectrum subchannels, each of which can be given a different priority and therefore a different threshold. In this case, three different thresholds are given. The modem's transmission rate is 9.7Mbps in the 6MHz band. Indoor transmission tests confirm that lows (weighted power layer I), middles (averaged power layer II), and highs (lightened power layer III) are retrievable under conditions in which the desired to undesired signal ratios (DURs) are respectively 0dB, 8.5dB, and 13.5dB. If the undesired signals are multipaths, these performances are dramatically improved by Rake combining and EQ. The AW-CDM system can be used for 20-30 Mbps advanced television (ATV) transmission in the 6-MHz bandwidth simply by changing the binary inputs into quaternary or octonary inputs.

In this paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.

This paper develops a prediction model for evaluating the influence of propagation attenuation due to aircraft's flying across the earth-satellite link. This prediction model is based on the Aperture-field method of Huygens-Fresnel wave theory. Considering arriving and taking off course around airport, attenuation impairment is calculated for different types of aircrafts and flight directions. In order to verify this model's accuracy, numerical results are compared with measurement values. The calculations agree well with the measurements. Ground antenna directivity and anticipated impairment to digital broadcasting system such as Perfect TV are also discussed.